#include <stdio.h>

#define MAX_ROW 5
#define MAX_COL 5

struct point { int row, col; } stack[512];
int top = 0;

struct point history[512];
int history_len = 0;

void push(struct point p) {
    stack[top++] = p;
}

struct point pop(void) {
    struct point p = stack[--top];
    history[history_len++] = p;
    return p;
}

int is_empty(void) {
    return top == 0;
}

int maze[MAX_ROW][MAX_COL] = {
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0,
};

void print_maze(void) {
    int i, j;
    for (i = 0; i < MAX_ROW; i++) {
        for (j = 0; j < MAX_COL; j++)
            printf("%d ", maze[i][j]);
        putchar('\n');
    }
    printf("*********\n");
}

void visit(int row, int col) {
    struct point visit_point = { row, col };
    maze[row][col] = 2;
    push(visit_point);
}

int main(void) {
    struct point p = { 0, 0 };
    struct point path[512];
    int path_len = 0;
    int diff_row, diff_col;
    maze[p.row][p.col] = 2;
    push(p);

    while (!is_empty()) {
        p = pop();
        if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1)
            break;
        if (p.col+1 < MAX_COL && maze[p.row][p.col+1] == 0)
            visit(p.row, p.col+1);
        if (p.row+1 < MAX_ROW && maze[p.row+1][p.col] == 0)
            visit(p.row+1, p.col);
        if (p.col-1 >= 0 && maze[p.row][p.col-1] == 0)
            visit(p.row, p.col-1);
        if (p.row-1 >= 0 && maze[p.row-1][p.col] == 0)
            visit(p.row-1, p.col);
        print_maze();
    }

    if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
        path[path_len++] = p;
        struct point current = p;
        for (int i = history_len - 2; i >= 0; i--) {
            struct point prev = history[i];
            diff_row = prev.row - current.row;
            if (diff_row < 0) diff_row = -diff_row;
            diff_col = prev.col - current.col;
            if (diff_col < 0) diff_col = -diff_col;
            if ((diff_row == 1 && diff_col == 0) || (diff_col == 1 && diff_row == 0)) {
                path[path_len++] = prev;
                current = prev;
                if (current.row == 0 && current.col == 0) break;
            }
        }
        printf("正向路径:\n");
        for (int i = path_len - 1; i >= 0; i--) {
            printf("(%d, %d) ", path[i].row, path[i].col);
            if (i % 5 == 0) putchar('\n');
        }
    } else {
        printf("No path!\n");
    }

    return 0;
}